#include <vector>
#include <algorithm>

//mad算法 去除离群值
template<typename T>
T Mad(std::vector<T> nums, float s) {
    int n = nums.size();
    int c = 0;
    if (n < 2) {
        return nums[0];
    }
    std::sort(nums.begin(), nums.end());
    float median = (n % 2 == 1) ? nums[n / 2] : (nums[n / 2] + nums[n / 2 - 1]) / 2; //中位数
    std::vector<T> deviations;
    float new_nums = 0; //偏差值
    deviations.reserve(n);
    for (int i = 0; i < n; i++) {
        deviations.push_back(abs(nums[i] - median));
    }
    std::sort(deviations.begin(), deviations.end());
    float mad = (n % 2 == 1) ? deviations[n / 2] : (deviations[n / 2] + deviations[n / 2 - 1]) / 2;
    for (size_t i = 0; i < n; i++) {
        if (abs(nums[i] - median) < s * mad) {
            new_nums += (nums[i]);
            c++;
        }
    }
    if (c)
        return new_nums / (T) c;
    else
        return median;
}

template<typename T>
T Mad_static(T *nums, size_t N, float s) {
    size_t n = N;
    size_t c = 0;
    if (n < 2) {
        return nums[0];
    }
    std::sort(nums, nums + n);
    float median = (n % 2 == 1) ? nums[n / 2] : (nums[n / 2] + nums[n / 2 - 1]) / 2; //中位数
    float deviations[N];
    float new_nums = 0; //偏差值
    for (size_t i = 0; i < n; i++) {
        deviations[i] = std::abs(nums[i] - median);
    }
    std::sort(deviations, deviations + n);
    float mad = (n % 2 == 1) ? deviations[n / 2] : (deviations[n / 2] + deviations[n / 2 - 1]) / 2;
    for (size_t i = 0; i < n; i++) {
        if (std::abs(nums[i] - median) < s * mad) {
            new_nums += nums[i];
            c++;
        }
    }
    if (c)
        return new_nums / static_cast<T>(c);
    else
        return median;
}

template int Mad<int>(std::vector<int> nums, float s);
